Some applications provide query interfaces that allow a user to define Boolean expressions that include multiple conditions for selecting data from a computer system, such as a database system or a file system. For example, the Boolean expressions can be written in a standard query language (SQL). They are then sent to the computer system, where they are executed. Examples of such a computer system are described in the patent applications WO 02/061612 and WO 02/061613. A Boolean expression can include multiple conditions which are combined by Boolean operators. A condition typically includes an attribute name, an operator, and a value or a value range.
For example, the following three conditions referring to the attribute birth_date may be combined with AND or OR operators.
birth_date between 1938 and 1990
birth_date <=1940
birth_date >1920
Advantageously, within the system the complete Boolean expression is processed in disjunctive or conjunctive normal form. In this example, it is assumed that all conditions are combined with a Boolean AND or that all conditions are combined with a Boolean OR. If there are many conditions in the Boolean expression, it may happen intentionally or unintentionally that some of the conditions refer to the same attribute.
Some combinations of conditions referring to the same attribute may either lead to uninteresting results for logical reasons or cause more conditions than necessary to be passed to the computer system. The following cases may be distinguished:
Null set: The result set is empty (zero records found). This may happen if all the conditions are combined with AND.
Entire search domain: The result set consists of all records loaded into or stored in the computer system, so the selectivity is zero. This may happen if the conditions are combined with OR.
More conditions than necessary: two or more of conditions referring to the same attribute have an overlap with respect to their selectivity. That is, there is some redundancy in the conditions of the Boolean expression.